/*
 * @lc app=leetcode.cn id=142 lang=cpp
 *
 * [142] 环形链表 II
 *
 * 方法1：快慢指针 + 相交链表思想
 * - 当 fast 与 slow 第一次相交时，slow一定位于圈内
 * - 问题：虽然为 O(N)，但是要圈数较多
 * 
 * 官方题解：快慢指针的移动数量关系
 * - 当 fast 与 slow 第一次相交时，fast移动的距离为slow的两倍 -> head到交点与slow相差环长的倍数 
 */

#include <iostream>
#include <vector>

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// @lc code=start
class Solution
{
public:
    ListNode *detectCycle_01(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return nullptr;

        ListNode *slow = head;
        ListNode *fast = head->next;
        while (slow != fast)
        {
            if (fast == nullptr || fast->next == nullptr)
                return nullptr;

            slow = slow->next;
            fast = fast->next->next;
        }

        /* 求相交链表的交点 */
        fast = head;
        ListNode *end = slow;
        slow = slow->next;

        while (slow != fast)
        {
            slow = (slow == end) ? head : slow->next;
            fast = (fast == end) ? end->next : fast->next;
        }

        return slow;
    }

    ListNode *detectCycle_00(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return nullptr;

        ListNode *slow = head;
        ListNode *fast = head->next;
        while (slow != fast)
        {
            if (fast == nullptr || fast->next == nullptr)
                return nullptr;

            slow = slow->next;
            fast = fast->next->next;
        }

        /* 求相交链表的交点 */
        fast = head;
        while (slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;

    std::vector<int> head_nums = {1, 5, 6, 3, 2, 0, -4};
    int pos = 2;

    /* 构建链表 */
    ListNode *p = nullptr;
    ListNode *head = nullptr;
    ListNode *rear = nullptr;
    for (auto n : head_nums)
    {
        if (head == nullptr)
        {
            head = new ListNode(n);
            rear = head;
        }
        else
        {
            rear->next = new ListNode(n);
            rear = rear->next;
        }

        if (n == pos)
            p = rear;
    }
    rear->next = p;

    p = solution.detectCycle_00(head);
    std::cout << p->val << std::endl;

    /* 删除链表 */
    rear->next = nullptr;
    while (head != nullptr)
    {
        p = head;
        head = head->next;
        delete p;
    }

    return 0;
}